#pragma once

#include <utility>
#include <functional>

#include "../allocator/alloc.h"
// For Pair
#include "Pair.h"

// For binary_function tag For _SelectFirst
#include "../function/function.h"
#include "RB-Tree.h"

// Map 不允许两个元素拥有相同的Key

template <typename Key, typename T, typename Compare = std::less<Key>,
          typename Alloc = alloc>
class map
{
public:
    using key_type = Key;
    using data_type = T;
    using mapped_type = T;
    // map 的 Key 是 const Key 类型
    // 一旦修改了Key, 整颗红黑树迭代器失效
    using value_type = hamster::pair<const Key, T>;
    using key_compare = Compare;

    class value_compare : public binary_function<value_type, value_type, bool>
    {
        // 申明了友元类
        friend class map<Key, T, Compare, Alloc>;

    protected:
        Compare comp;
        // 构造函数为protect，意味着只有友元类可以直接创建实例
        value_compare(Compare c) : comp(c) {}

    public:
        bool operator()(const value_type &x, const value_type &y) const
        {
            return comp(x.first, y.first);
        }
    };

private:
    //  Key_Type Value_Type KeyOfValue Compare Alloc
    //  KeyOfValue就是通过value来获得key，这里就应该返回一个key的类型，即从一个pair中获得第一个元素
    using rep_type = rb_tree<key_type, value_type, _Select1st<value_type>, key_compare, Alloc>;
    // Map 底层是一个红黑树
    rep_type t;

public:
    // type_traits
    using pointer = typename rep_type::pointer;
    using const_pointer = typename rep_type::const_pointer;
    using reference = typename rep_type::reference;
    using const_reference = typename rep_type::reference;
    // 因为可以修改Key对应的Value, 但是不可以修改Key
    using iterator = typename rep_type::iterator;
    using const_iterator = typename rep_type::const_iterator;
    using reverse_iterator = typename rep_type::reverse_iterator;
    using const_reverse_iterator = typename rep_type::const_reverse_iterator;
    using size_type = typename rep_type::size_type;
    using difference_type = typename rep_type::difference_type;

    // 在Map中因为Key是唯一的，因此只能调用红黑树的insert_unique方法

    // allocation / deallocation
    map() : t(Compare()) {}

    explicit map(const Compare &comp) : t(comp) {}

    template <typename InputIterator>
    map(InputIterator first, InputIterator last) : t(Compare())
    {
        t.insert_unique(first, last);
    }

    template <typename InputIterator>
    map(InputIterator first, InputIterator last, const Compare &comp) : t(comp)
    {
        t.insert_unique(first, last);
    }

    map(const map<Key, T, Compare, Alloc> &x) : t(x.t) {}

    map<Key, Compare, Alloc> &operator=(const map<Key, Compare, Alloc> &x)
    {
        t = x.t;
        return *this;
    }

    // RB-Tree都已经提供了相应的调用接口
    key_compare key_comp() const { return t.key_comp(); }

    value_compare value_comp() const { return value_compare(t.key_comp()); }

    iterator begin() { return t.begin(); }
    const_iterator begin() const { return t.begin(); }

    iterator end() { return t.end(); }
    const_iterator end() const { return t.end(); }

    reverse_iterator rbegin() { return t.rbegin(); }
    const_reverse_iterator rbegin() const { return t.rbegin(); }

    reverse_iterator rend() { return t.rend(); }
    const_reverse_iterator rend() const { return t.rend(); }

    bool empty() const { return t.empty(); }

    size_type size() const { return t.size(); }
    size_type max_size() const { return t.max_size(); }

    void swap(map<Key, T, Compare, Alloc> &x)
    {
        t.swap(x.t);
    }

    // insert a pair
    hamster::pair<iterator, bool> insert(const value_type &x)
    {
        return t.insert_unique(x);
    }

    // T& operator[](const key_type& k)
    // {
    //     // // no key insert one
    //     // hamster::pair<iterator, bool> insert_res = insert(value_type(k, T()));
    //     // // insert_res是一个包含插入位置的迭代器和插入是否成功的bool值
    //     // // insert_res.first取出了插入位置的迭代器
    //     // // insert_res.first的类型为rep_type::iterator
    //     // // rep_type::iterator类型就是__rb_tree_iterator<Value, reference, pointer>
    //     // // __rb_tree_iterator<Value, reference, pointer>继承自__rb_tree_base_iterator
    //     // // __rb_tree_base_iterator中有一个具体指向node的节点中存储了value的Value_filed的value值
    //     // // node的类型就是Value_type就是一个pair,因此取出pair的第二个值就是key所对应的value
    //     // return (*((insert(value_type(k,T()))).first)).second;
    //     return (*((insert(value_type(k, T()))).first)).second;
    // }
    T& operator[](const key_type &__k)
    { // 访问指定的元素
        iterator __i = lower_bound(__k);
        // __i->first is greater than or equivalent to __k.
        if (__i == end() || key_comp()(__k, (*__i).first))
            __i = insert(__i, value_type(__k, T()));
        return (*__i).second; // 实值以 by reference 方式传递
    }

    template <typename InputIterator>
    void insert(InputIterator first, InputIterator last)
    {
        return t.insert_unique(first, last);
    }

    // 在具体位置进行insert需要插入一个pair
    iterator insert(iterator position, const value_type &x)
    {
        return t.insert_unique(position, x);
    }

    void erase(iterator position) { t.erase(position); }
    // 移除key对应的所有节点返回一个移除之后的数目
    size_type erase(const key_type &x) { return t.erase(x); }
    void erase(iterator first, iterator last) { return t.erase(first, last); }

    // find
    iterator find(const key_type &x) { return t.find(x); }
    const_iterator find(const key_type &x) const { return t.find(x); }

    size_type count(const key_type &x) const { return t.count(x); }

    iterator lower_bound(const key_type &x) { return t.lower_bound(x); }
    const_iterator lower_bound(const key_type &x) const { return t.lower_bound(x); }

    iterator upper_bound(const key_type &x) { return t.upper_bound(x); }
    const_iterator upper_bound(const key_type &x) const { return t.upper_bound(x); }

    hamster::pair<iterator, iterator> equal_range(const key_type &x) { return t.equal_range(x); }
    hamster::pair<const_iterator, const_iterator> equal_range(const key_type &x) const { return t.equal_range(x); }

    // 这里因为红黑树t被声明为了private，因此必须声明为friend函数，外部inline函数才能访问到内部的t
    template <typename _Key, typename _T, typename _Compare, typename _Alloc>
    friend bool operator==(const map<_Key, _T, _Compare, _Alloc> &, const map<_Key, _T, _Compare, _Alloc> &);
    
    template <typename _Key, typename _T, typename _Compare, typename _Alloc>
    friend bool operator<(const map<_Key, _T, _Compare, _Alloc> &, const map<_Key, _T, _Compare, _Alloc> &);

    // T &operator[](const key_type &__k)
    // { // 访问指定的元素
    //     iterator __i = lower_bound(__k);
    //     // __i->first is greater than or equivalent to __k.
    //     if (__i == end() || key_comp()(__k, (*__i).first))
    //         __i = insert(__i, value_type(__k, T()));
    //     return (*__i).second; // 实值以 by reference 方式传递
    // }
};

template <typename Key, typename T, typename Compare, typename Alloc>
inline bool operator==(const map<Key, T, Compare, Alloc> &x,
                       const map<Key, T, Compare, Alloc> &y)
{
    return x.t == y.t;
}
template <typename Key, typename T, typename Compare, typename Alloc>
inline bool operator<(const map<Key, T, Compare, Alloc> &x,
                      const map<Key, T, Compare, Alloc> &y)
{
    return x.t < y.t;
}
